package code20210926;


public class C740 {

	public static void main(String[] args) {
		int[] nums = {3,4,2};
		System.out.println(new C740().deleteAndEarn(nums));
	}
	public int deleteAndEarn(int[] nums) {
		int n = nums.length;
		int[][] dp = new int[n+1][n+1];
		
		for(int i=1;i<=n;i++) {
			dp[0][i] = dp[i][0] = 0;
		}
		
		for(int i=1;i<=n;i++) {
			int pre = nums[i-1];
			for(int j=1;j<=n;j++) {
				if(i!=j) {
					if(pre!=(nums[j-1]+1)&&pre!=(nums[j-1]-1)) dp[i][j] = Math.max(dp[i][j-1]+nums[j-1],dp[i-1][j]+nums[i-1]);
					else dp[i][j] = dp[i][j-1];
				}
			} 
		}
		return dp[n][n];
		
    }
}
